P5017 摆渡车

这道题我们先看一下数据范围:n500,m100,0ti4×106n≤500,m≤100,0≤t_i≤4×10^6

显然复杂度和n,mn,m有关,既然如此,我们考虑用tt的复杂度来解决此题吧。(此题解法不止一种)

我们用dp[i]dp[i]表示在ii时刻发车(不管是第几次),所有在ii时刻之前到达的人的等待时间之和。tot[i]tot[i]表示第ii时刻有多少人开始等车,显然有:

阅读全文 »

CF45G Prime Problem

前置知识:哥德巴赫猜想:任一大于2的偶数都可写成两个质数之和

然后,这道题就非常水了。

S=1+2+...+nS=1+2+...+n , 我们分类讨论 SS 的情况就好了。

阅读全文 »

P3232 [HNOI2013]游走

这道题边的数量最高是10000多,而点只有500,这提醒我们,我们不能直接对边求期望,而是点。

Expection[u]Expection[u]表示点uu的期望走过次数,Degree[u]Degree[u]表示点uu的度数。

那么,

阅读全文 »

CF85E Guard Towers

注意题目中的这句话 : 使得同组内的两座塔的曼哈顿距离的最大值最小 , 很容易想到二分。

考虑二分一个长度lenlen,显然,当两个点的曼哈顿距离大于lenlen时,它们不能属于同一个集合。

我们将这样的点对连一条边,原问题等价与判断新图是否为一个二分图

阅读全文 »

CF559C Gerald and Giant Chess

如果没有不能走到的点,这道题就非常简单了。我们只需向下走h1h-1步,向右走w1w-1步,就可到达右下角。在这h+w2h+w-2步中,我们选h1h-1向下走,那么答案为Ch+w2h1C_{h+w-2}^{h-1}

但是,棋盘中有些点是不能走的,我们考虑用容斥原理去除多余方案,即

Ans=Ch+w2h1P1+P2+..+(1)nPnAns=C_{h+w-2}^{h-1}-P_1+P_2+..+(-1)^n * P_n

阅读全文 »

CF167E Wizards and Bets

首先,我们将所有源点与汇点筛出来,然后从每一个源点dfs求出它到各汇点的路径数,题目中保证源点与汇点数量相同,我们记为cntcnt
那么,我们可以得到一个cntcntcnt * cnt的矩阵。

先考虑路径不相交的情况(似乎大家思路都是这样),题目求的是一个排列的逆序对数,记为τ(σ)\tau(\sigma)。那么,题目等价于求:

阅读全文 »

P1769 淘汰赛制

与题目定义有些不同,nn表示人数,mm表示淘汰赛轮数。题目显然输入的是mm,根据它算出nn。为了方便2进制计算,编号从00~n1n-1。最后答案加1即可。同时,比赛胜败概率为了方便先除以100,用doubledouble计算。

现在考虑如何计算答案,设a[i][j]a[i][j]iijj的胜率,f[i][j]f[i][j]为第iijj胜出的概率。那么有:

f[i][j]=kf[i1][j]×f[i1][k]×a[j][k]f[i][j]= \sum_{k} f[i-1][j] \times f[i-1][k] \times a[j][k]

阅读全文 »

CF147B Smile House

貌似 @DDF_Van 大佬的标程过不了 , 有些题解用的二分会多一个lognlog_n,那就补一发倍增题解吧。

Solution 1

dp[s][i][j]dp[s][i][j]表示走了不多于ss条边,iji \to j的最大边权(走不通为极小值)

阅读全文 »